package interview.greatestCommonFactor;

/**
 * 九章算术
 */
public class Gcb {

    /**
     * 九章算术中求最大公约数
     * @param a 整数 a
     * @param b 整数 b
     * @return 最大公约数
     */
    public static int gcb(int a,int b){
        if (a == b){
            return a;
        }
        //全是偶数  一奇一偶  全奇数
        if ((a & 1 )== 0 && (b & 1) == 0){
            //将两个数全部位运算之后 得出的结果需要补0在返回
            return gcb(a>>1,b>>1) << 1;
        } else if ((a & 1) != 0 && (b & 1) == 0){
            return gcb(a,b>>1);
        } else if ((a & 1) == 0 && (b & 1) != 0){
            return gcb(a>>1,b);
        } else {
            int big = a > b ? a : b;
            int min = a < b ? a : b;
            return gcb(big - min,min);
        }
    }
}
